Halftoning is a technique that is commonly used in digital imaging to create the appearance of intermediate tones when only two colorant levels (i.e., ink or no ink) are available. Halftoning methods rely on the fact that an observer's eye will spatially average over some local area of the image so that intermediate tone levels can be created by turning some of the pixels "on" and some of the pixels "off" in some small region. The fraction of the pixels which are turned on will determine the apparent gray level. Examples of common halftoning techniques include ordered dither and error-diffusion.
The ordered dither technique is typically implemented by forming a dither matrix having M.sub.x .times.M.sub.y elements which is tiled across the image. The elements of the dither matrix are distributed across the range of expected input tone values so that the full range of tones can be reproduced. A basic flow chart for this approach is shown in FIG. 1. A given pixel in the image has column and row addresses x and y, respectively, and an input pixel value I(x,y). Modulo operators 10 are used to determine indices x.sub.d and y.sub.d that are used to address the dither matrix 12. The modulo operators 10 compute the value x.sub.d or y.sub.d by determining the remainder when the pixel address x or y is divided by the dither matrix dimension M.sub.x or M.sub.y respectively. This process is referred to as "modularly addressing" the dither matrix. The dither value d(x.sub.d,y.sub.d) stored in the dither matrix at this address is then compared to the input pixel value I(x,y) using a comparator 14. If the input pixel value is below the dither value, the output pixel value O(x,y) is set to "off"; if the value is above the dither value, the output pixel value O(x,y) is set to "on".
A second implementation of this basic technique is shown in FIG. 2. In this case the dither value d(x.sub.d,y.sub.d) is combined with the input pixel value I(x,y) using an adder 24. A threshold operator 26 is then used to threshold the combined value to determine the output pixel value O(x,y). If the combined value is below the threshold, the pixel is set to "off"; if the combined value is greater, the output is set to "on."
Yet another implementation of this basic technique is shown in FIG. 3. In this case a set of k dither bitmaps 32 are formed corresponding to the halftone patterns formed when the dither matrix is thresholded at each input level k. The input pixel value I(x,y) is then used to select which of the dither bitmaps should be used for each pixel. Modulo operators 30 are used to determine indices x.sub.d and Y.sub.d that are used to address the selected dither bitmap to determine the output pixel value O(x,y). This implementation has the advantage that fewer computations are necessary to process each pixel. It should be noted that any dither pattern which can be implemented using the methods of FIG. 1 and FIG. 2 can also be implemented using the method of FIG. 3. However, it is possible to define a set of dither bitmaps for the method of FIG. 3 which could not be implemented using the other methods. This is because in the dither matrix implementations shown in FIGS. 1 and 2, once a certain pixel is turned on at the input value corresponding to the dither value, it will stay on for all higher input values. With the dither bitmaps approach shown in FIG. 3, this constraint is not present. For example, a certain pixel could be "off" for an input value of 150, "on" for an input value of 151, and "off" again for an input value of 152.
A variety of different dither matrices have been used in the past which create resulting images with differing visual characteristics. Common types include random dither matrices, clustered-dot dither matrices, and Bayer (dispersed dot) dither matrices. Sullivan and Miller (U.S. Pat. No. 4,920,501) have recently introduced a technique to design dither bitmaps which have minimum visual modulation. These patterns are sometimes called "blue-noise" patterns. They are attractive in that the patterns that are produced have minimum visibility to human observers, and as a result the images produced are visually pleasing relative to images produced using other patterns. The basic procedure involved in the creation of these patterns is to use an optimization technique, such as stochastic annealing, to determine the arrangement of the matrix elements which minimizes some cost function based upon weighting the frequency components of the halftone patterns with a human visual sensitivity function. Sullivan and Ray have also disclosed an enhancement to this method which insures that the bitmaps for each of the gray levels are correlated in such a way that they can be implemented using a dither matrix (U.S. Pat. No. 5,214,517). Other extensions to this basic approach include a method for simultaneously optimizing all of the gray levels (see U.S. patent application, Ser. No. 07/848,779 by Ray), and a method for designing blue-noise dither matrices for use with multi-level output devices (see U.S. patent application, Ser. No. 08/331,246 by Spaulding and Ray).
Parker and Mitsa (U.S. Pat. No. 5,111,310) and Lin (U.S. Pat. No. 5,317,418 and 5,469,515) have also recently introduced techniques for the design of dither patterns. Although the actual optimization methods that they have used are somewhat different, the resulting patterns are quite similar to those created using the methods described in the Sullivan et al. patents.
When producing color images on binary output devices it is necessary to halftone each of the color channels. Typically the color planes are cyan, magenta and yellow (CMY), or cyan, magenta, yellow and black (CMYK). If the same halftoning pattern is used for each of the color channels this is known as "dot-on-dot" printing. This approach is rarely used in practice because it results in a higher level of luminance modulation, and additionally the color reproduction characteristics will be more sensitive to registration errors. The higher level of luminance modulation will cause the halftone patterns to be more visible than one of the color channels printed alone. The increased sensitivity to registration errors may cause the reproduced color to drift page to page, or even within a page, as the registration characteristics of printing apparatus change. In the graphic arts field the preferred solution has typically been to decorrelate the halftone patterns by rotating the halftone patterns to different "screen angles." For conventional graphic arts halftone methods, this rotation can either be accomplished optically or digitally.
A number of techniques have been suggested for decorrelating the halftone patterns used for ordered dither (for example see U.S. Pat. No. 5,341,228). These include using independently derived dither matrices for each color channel, spatially shifting the dither matrix patterns for each color plane relative to a reference dither matrix, and using an inverse dither matrix for one or more of the color channels. Each of these techniques has advantage that the halftone patterns for the different color channels will be decorrelated, and therefore the resulting halftone image should produce lower amounts of luminance modulation and sensitivity to registration errors relative to the nominal dot-on-dot printing case. However, none of these techniques will produce images that will exhibit optimal appearance, particularly with respect to the visibility of the halftone patterns.